//https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/submissions/575096794/

class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        string num = to_string(n);  // 将整数 n 转换为字符串，方便逐位处理
        int res = 0;

        // 统计所有位数小于 n 的数字的组合数量
        for (int i = 1; i < num.length(); ++i)
            res += pow(digits.size(), i); // 每个位置可以选择 digits.size() 个数字，共有 pow(digits.size(), i) 种组合

        bool flag = true;
        // 逐位比较，处理与 n 位数相同的情况
        for (int i = 0; i < num.size(); ++i) {
            string a {num[i]}; // 当前位的字符
            int b = pow(digits.size(), num.size() - i - 1); // 剩余位数的组合数量
            auto j = lower_bound(digits.begin(), digits.end(), a); // 找到 digits 中大于等于 a 的第一个位置
            res += (j - digits.begin()) * b; // 统计当前位可以选择比 a 小的所有可能的组合数量
            if (j == digits.end() || *j > a) { // 如果 digits 中没有等于 a 的数字，说明无法继续匹配
                flag = false;
                break;
            }
        }
        res += flag; // 如果所有位都匹配成功，说明 n 本身也可以被表示，结果加 1
        return res;
    }
};